<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>与Client的交互 - 读论文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

        <!-- MathJax -->
        <script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><a href="chapter_1.html">读论文活动</a></li><li class="chapter-item expanded affix "><li class="part-title">6.824 分布式系统</li><li class="chapter-item expanded "><a href="Mapreduce.html"><strong aria-hidden="true">1.</strong> Mapreduce</a></li><li class="chapter-item expanded "><a href="GFS.html"><strong aria-hidden="true">2.</strong> GFS</a></li><li class="chapter-item expanded "><a href="VM-FT.html"><strong aria-hidden="true">3.</strong> VM-FT</a></li><li class="chapter-item expanded "><a href="Raft.html"><strong aria-hidden="true">4.</strong> Raft</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="Raft0.html"><strong aria-hidden="true">4.1.</strong> 感性认识Raft</a></li><li class="chapter-item expanded "><a href="Raft1.html"><strong aria-hidden="true">4.2.</strong> 什么是Raft？</a></li><li class="chapter-item expanded "><a href="Raft2.html"><strong aria-hidden="true">4.3.</strong> 复制状态机（Replicated State Machine）</a></li><li class="chapter-item expanded "><a href="Raft3.html"><strong aria-hidden="true">4.4.</strong> What's wrong with Paxos?</a></li><li class="chapter-item expanded "><a href="Raft4.html"><strong aria-hidden="true">4.5.</strong> 向可理解性进军</a></li><li class="chapter-item expanded "><a href="Raft5.html"><strong aria-hidden="true">4.6.</strong> Raft共识算法（零）</a></li><li class="chapter-item expanded "><a href="Raft6.html"><strong aria-hidden="true">4.7.</strong> Raft共识算法（一）——基础概念</a></li><li class="chapter-item expanded "><a href="Raft7.html"><strong aria-hidden="true">4.8.</strong> Raft共识算法（二）——选举leader</a></li><li class="chapter-item expanded "><a href="Raft8.html"><strong aria-hidden="true">4.9.</strong> Raft共识算法（三）——日志备份（log replication）</a></li><li class="chapter-item expanded "><a href="Raft9.html"><strong aria-hidden="true">4.10.</strong> Raft共识算法（四）——安全性和选举限制</a></li><li class="chapter-item expanded "><a href="Raft10.html"><strong aria-hidden="true">4.11.</strong> Raft共识算法（五）——如何提交之前term里的entry</a></li><li class="chapter-item expanded "><a href="Raft11.html"><strong aria-hidden="true">4.12.</strong> Raft共识算法（六）——安全性定理</a></li><li class="chapter-item expanded "><a href="Raft12.html"><strong aria-hidden="true">4.13.</strong> Raft共识算法（七）——如果follower/candidate宕机了</a></li><li class="chapter-item expanded "><a href="Raft13.html"><strong aria-hidden="true">4.14.</strong> Raft共识算法（八）——时间与可用性</a></li><li class="chapter-item expanded "><a href="Raft14.html"><strong aria-hidden="true">4.15.</strong> 成员变更</a></li><li class="chapter-item expanded "><a href="Raft15.html"><strong aria-hidden="true">4.16.</strong> 日志压缩</a></li><li class="chapter-item expanded "><a href="Raft16.html" class="active"><strong aria-hidden="true">4.17.</strong> 与Client的交互</a></li><li class="chapter-item expanded "><a href="Raft17.html"><strong aria-hidden="true">4.18.</strong> 实验时遇到的bug</a></li><li class="chapter-item expanded "><a href="Raft18.html"><strong aria-hidden="true">4.19.</strong> 总结</a></li></ol></li><li class="chapter-item expanded "><a href="Zookeeper.html"><strong aria-hidden="true">5.</strong> Zookeeper</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="linearizability1.html"><strong aria-hidden="true">5.1.</strong> 线性一致性（一）——基础概念</a></li><li class="chapter-item expanded "><a href="linearizability2.html"><strong aria-hidden="true">5.2.</strong> 线性一致性（二）——细究linearizability</a></li><li class="chapter-item expanded "><a href="zk_intro.html"><strong aria-hidden="true">5.3.</strong> 引言</a></li><li class="chapter-item expanded "><a href="zk_service.html"><strong aria-hidden="true">5.4.</strong> Zookeeper Service</a></li><li class="chapter-item expanded "><a href="zk_api.html"><strong aria-hidden="true">5.5.</strong> Zookeeper API</a></li><li class="chapter-item expanded "><a href="zk_prop.html"><strong aria-hidden="true">5.6.</strong> Zookeeper的性质</a></li><li class="chapter-item expanded "><a href="zk_ex.html"><strong aria-hidden="true">5.7.</strong> 基于Zookeeper实现锁</a></li></ol></li><li class="chapter-item expanded "><a href="CRAQ.html"><strong aria-hidden="true">6.</strong> CRAQ</a></li><li class="chapter-item expanded "><a href="lamport_clock.html"><strong aria-hidden="true">7.</strong> Time, Clocks, and the Ordering of Events in a Distributed System</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="lamport_clock1.html"><strong aria-hidden="true">7.1.</strong> 引言</a></li><li class="chapter-item expanded "><a href="lamport_clock_partial_order.html"><strong aria-hidden="true">7.2.</strong> 偏序关系</a></li><li class="chapter-item expanded "><a href="lamport_logic_clock.html"><strong aria-hidden="true">7.3.</strong> 逻辑时钟</a></li><li class="chapter-item expanded "><a href="lamport_total_order.html"><strong aria-hidden="true">7.4.</strong> 全序关系</a></li><li class="chapter-item expanded "><a href="lamport_clock_ana_behave.html"><strong aria-hidden="true">7.5.</strong> 异常事件</a></li><li class="chapter-item expanded "><a href="lamport_p_clock.html"><strong aria-hidden="true">7.6.</strong> 物理时钟</a></li><li class="chapter-item expanded "><a href="lamport_end.html"><strong aria-hidden="true">7.7.</strong> 结论</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">6.828 操作系统</li><li class="chapter-item expanded "><a href="828intro.html"><strong aria-hidden="true">8.</strong> Killer of Microseconds</a></li><li class="chapter-item expanded "><a href="cloudlab.html"><strong aria-hidden="true">9.</strong> CloudLab</a></li><li class="chapter-item expanded "><a href="dpdk.html"><strong aria-hidden="true">10.</strong> DPDK</a></li><li class="chapter-item expanded "><a href="spdk.html"><strong aria-hidden="true">11.</strong> SPDK</a></li><li class="chapter-item expanded "><a href="Shenango.html"><strong aria-hidden="true">12.</strong> Shenango</a></li><li class="chapter-item expanded "><a href="TritonSort.html"><strong aria-hidden="true">13.</strong> TritonSort</a></li><li class="chapter-item expanded "><a href="Profiling.html"><strong aria-hidden="true">14.</strong> Profiling a warehouse-scale computer</a></li><li class="chapter-item expanded affix "><li class="part-title">6.828 - Network</li><li class="chapter-item expanded affix "><li class="part-title">CS244 - Advanced Topics in Networking</li><li class="chapter-item expanded "><a href="DARPA_NET.html"><strong aria-hidden="true">15.</strong> The Design Philosophy of The DARPA Internet Protocols</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="DARPA_NET2.html"><strong aria-hidden="true">15.1.</strong> Second Level Goals</a></li><li class="chapter-item expanded "><a href="DARPA_NET3.html"><strong aria-hidden="true">15.2.</strong> Types of Service</a></li><li class="chapter-item expanded "><a href="DARPA_NET4.html"><strong aria-hidden="true">15.3.</strong> Varieties of Networks</a></li><li class="chapter-item expanded "><a href="DARPA_NET5.html"><strong aria-hidden="true">15.4.</strong> Architecture and Implementation</a></li><li class="chapter-item expanded "><a href="DARPA_NET6.html"><strong aria-hidden="true">15.5.</strong> Datagrams</a></li></ol></li><li class="chapter-item expanded "><li class="part-title">最后</li><li class="chapter-item expanded "><a href="end.html"><strong aria-hidden="true">16.</strong> 最后</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">读论文</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="与client的交互"><a class="header" href="#与client的交互">与Client的交互</a></h1>
<p>本小节将阐述client是如何与raft进行交互的，包括client是如何发现集群leader，以及raft是如何支持线性一致性语义（linearizable semantics）的。<br />
这些问题都是基于共识协议系统的基础问题，而raft的解决方案和其他的系统也都大差不差。</p>
<p>raft的客户端只向leader发送请求。当一个client开始启动后，它先随机连接系统里的一个server。如果client与之通信的server不是一个leader，这个server就会拒绝响应client的请求，并且提供leader（如果有）的信息。</p>
<blockquote>
<p>If the client’s first choice is not the leader, that server will reject the client’s request and supply information about the most recent leader it has heard from (AppendEntries requests include the network address of the leader).<br />
【论文里这句话很绕，supply information about the most recent leader it has heard from(AppendEntries requests include the network address of the leader)，提供最近给它发送心跳包的那个leader的信息，AppendEntries请求里包含了leader在网络里的地址】</p>
</blockquote>
<p>如果leader宕机了，client的请求就会超时；client就会重新随机选一个server进行通信。</p>
<p>Raft的另一个目标是实现线性语义（每一个操作都是立即地，只执行一次的，即只在调用它的时刻与请求返回的时刻之间，只执行一次）。<br />
然而，论文写到这里，raft其实还是有可能会重复把一个command执行多次的。（是的！作为一个尝试复现raft的读者，我也逐渐开始意识到这个问题）<br />
<strong>举个例子，如果leader在提交entry之后宕机，但没来得及向client发送response，client就会尝试重新向新的leader发送这条command，这样的话就会导致一条命令执行了两次。</strong><br />
解决这个问题的关键就是给每一个命令分配一个唯一的序列号。如此一来，状态机可以通过比对之前的response，来定位最新的命令序列号是什么。<br />
如果server收到了一个该序列号已经被执行过的命令，它就会立即返回而不再重复执行这条请求。</p>
<p>只读操作不会更改log里的数据。<br />
然而，如果没有额外的措施，可能会存在client读到过期数据的风险，因为leader响应的这个request的时候，可能它已经被另一个新的leader取代了而不自知。<br />
线性化读操作要求一定不能返回过期数据，raft需要引入两个额外的预防措施在不使用log的情况下来保证不返回过期数据。<br />
第一，leader必须知道哪些entry已经被提交了。<br />
Leader完整性保证了leader拥有全部的已提交entry，但是在term最开始的时候，它可能会不确定一些entry是否已经被提交。<br />
为了搞清楚这个事情，新的leader需要在它的term内去提交一条新的entry。<br />
Raft规定，每个term里，刚竞选成功的leader在一开始，需要在log里提交一个空的no-op entry，从而来解决这个问题。<br />
第二，leader在处理一个只读的请求之前，必须先确认它自己是否已经被罢免了（如果一个新leader被选出来了，那么它所读到的数据可能就是一个过期数据）。<br />
Raft规定，如果一个leader要处理一个只读请求，那它必须先发送心跳信息，当它收到集群中过半的返回消息之后，才能去处理这个只读请求，从而保证它不会返回过期数据。<br />
另一种可选方案是心跳机制可以提供一个租约（lease），leader依据这个租约来响应请求，但是如此一来的话时间就和安全性挂钩了（可能会有时钟偏差）。</p>
<blockquote>
<p><strong>额外的话</strong>：<br />
这一小节解决了我的若干疑惑。</p>
<ol>
<li>Q: client向系统发送请求，系统成功commit了，但是返回超时；client再发送相同的命令，系统应该怎么办？<br />
A: raft的请求应该是保证幂等的，幂等的意思是 <code>f(f(x)) = f(x)</code>，如果系统里的leader收到client的命令，发现这个命令它已经处理过了，那它就直接返回true，但不做任何处理。</li>
<li>Q: leader如何知道哪些entry已经被提交了？<br />
A: 为了搞清楚这个事情，新的leader需要在它的term内去提交一条新的entry。Raft规定，每个term里，刚竞选成功的leader在一开始，需要在log里提交一个空的no-op entry，从而来解决这个问题。
（这个和raft官网上的可视化模型表现不符。官网上的演示模型，如果不提交新的request，leader就不commit前任leader留下的entry。）<br />
<strong>在824的lab框架里，client发送的command是interface类型。我为了实现no-op特性，声明了一个type叫no-op。</strong><br />
此外，为了适配这种特性，我还特地区分了commandIndex和logIndex，commandIndex是给上层调用者client看的，logIndex是raft节点保存日志用的。<br />
不过我参考了网上其他人的代码，别人好像都没这么做。</li>
<li>Q: 如何避免leader给client返回过期的数据？<br />
A: <strong>Raft规定，如果一个leader要处理一个只读请求，那它必须先发送心跳信息，当它收到集群中过半的返回消息之后，才能去处理这个只读请求，从而保证它不会返回过期数据。</strong><br />
另一种可选方案是心跳机制可以提供一个租约（lease），leader依据这个租约来响应请求，但是如此一来的话时间就和安全性挂钩了（可能会有时钟偏差）。</li>
</ol>
<p>但是仍然有一些怪怪的地方，比如说我使用官网的演示模型。在如下情况中，leader宕机，entry不过半的情形下。</p>
<p><img src="./assets/raft_e6.png" alt="raft_e6" /></p>
<p>我可以构造出两种不一样的结果：term2里的entry被保留/被覆写。<br />
如下图：term2的entry被保留。</p>
<p><img src="./assets/raft_e7.png" alt="raft_e7" /></p>
<p>抑或是如下图：term2的entry被覆写。</p>
<p><img src="./assets/raft_e8.png" alt="raft_e8" /></p>
<p>我想，这篇论文里描述的raft安全性，应该是指，如果一个entry已经被提交。<br />
那么在大部分的server的log里面，在与这个entry相同的位置上，一定不会存在另一个不同内容的entry。<br />
而上述的这种情形，不违反论文里规定的安全性定义。</p>
</blockquote>
<blockquote>
<p>有了本节的知识，我们可以去做lab3了。
其实lab2的test给lab3提供了很好的参考。</p>
</blockquote>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="Raft15.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="Raft17.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="Raft15.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="Raft17.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
